package com.practice.dataStructure.list;

import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Objects;

public class LinkedList<E> implements List<E>{

    private int size;

    private Node<E> head;

    private Node<E> tail;

    @Override
    public void add(E element) {
        Node<E> node = new Node<>(element,tail,null);
        if(tail == null){
            head = node;
        }else{
            tail.next = node;
        }
        tail = node;
        size++;
    }

    @Override
    public void add(int index, E element) {
        if(index < 0 || index > size){
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        if(size == index){
            add(element);
            return;
        }
        Node<E> node = new Node<>(element,null,null);
        if(index == 0){
            node.next = head;
            head = node;
            return;
        }
        Node<E> pre = findNode(index-1);
        node.next = pre.next;
        pre.next = node;
        node.pre = pre;
        size++;
    }

    private Node<E> findNode(int index){
        Node<E> result = null;
        if(index < size/2){
            result = head;
            for(int i=0;i<index;i++){
                result = result.next;
            }
        }else{
            result = tail;
            for(int i=size-1;i>index;i--){
                result = result.pre;
            }
        }
        return result;
    }

    @Override
    public E get(int index) {
        if(index < 0 || index >= size){
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        return findNode(index).value;
    }

    @Override
    public E set(int index, E element) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        Node<E> node = findNode(index);
        E oldValue = node.value;
        node.value = element;
        return oldValue;
    }

    @Override
    public E remove(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        return removeNode(findNode(index));
    }

    private E removeNode(Node<E> node){
        Node<E> pre = node.pre;
        Node<E> next = node.next;
        if(pre == null){
            head = next;
        }else{
            pre.next = next;
        }
        if(next == null){
            tail = pre;
        }else{
            next.pre = pre;
        }
        node.pre = null;
        node.next = null;
        size--;
        return node.value;
    }

    @Override
    public boolean remove(E element) {
        Node<E> node = head;
        while(node != null){
            if(Objects.equals(node.value,element)){
                removeNode(node);
                return true;
            }
            node = node.next;
        }
        return false;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public Iterator<E> iterator() {
        return new LinkedListIterator();
    }

    class LinkedListIterator implements Iterator<E>{
        Node<E> current = head;

        @Override
        public boolean hasNext() {
            return current != null;
        }

        @Override
        public E next() {
            if(current == null){
                throw new NoSuchElementException();
            }
            E value = current.value;
            current = current.next;
            return value;
        }
    }

    class Node<e>{
        Node<E> pre;
        Node<E> next;
        E value;

        Node(E value){
            this.value = value;
            next = null;
            pre = null;
        }
        Node(E value,Node<E> pre,Node<E> next){
            this.next = next;
            this.pre = pre;
            this.value = value;
        }
    }
}
